#include <stdio.h>
#include <stdlib.h>

/*
https://blog.csdn.net/weixin_63449996/article/details/124363899
realloc函数返回的是void*类型的指针，
指向在堆区重新开辟的内存块的起始地址，
memblock是先前开辟的内存块的指针
（也就是malloc或calloc之前申请的那块内存空间，即需要调整大小的内存空间），
size_t size指的是New size in bytes,新的字节数，注意不是增加的字节数，
而是新开辟的那块内存空间的字节数，返回值为调整之后的内存的起始地址。
*/
int min(int* a, int len)
{
	int i, min, x;
	min = 0;
	x = a[min];
	for(i=0; i < len; i++)
	{
		if(a[i] < x)
		{
			min = i;
		}
	}
	return a[min];
}

int max(int* a, int len)
{
	int i, max, x;
	max = 0;
	x = a[max];
	for(i=0; i < len; i++)
	{
		if(a[i] > x)
		{
			max = i;
		}
	}
	return a[max];
}
// 定义桶的数量
#define BUCKET_COUNT 10

// 定义桶的结构
typedef struct
{
	int count;
	int *padvalues;
}Bucket;

void bucketSort(int* arr, int n)
{
	// 创建桶数组
	Bucket adbuckets[BUCKET_COUNT];
	
	// 初始化桶
	for (int i = 0; i < BUCKET_COUNT; i++)
	{
		adbuckets[i].count = 0;
		adbuckets[i].padvalues = NULL;
	}
	
	// 将元素放入桶中
	for(int i = 0; i < n; i++)
	{
		int bucketIndex = arr[i] / BUCKET_COUNT;
		Bucket *ptbucket = &adbuckets[bucketIndex];
		
		// 扩展桶的容量
		ptbucket->padvalues = realloc(ptbucket->padvalues, (ptbucket->count + 1)*sizeof(int));
		ptbucket->padvalues[ptbucket->count] = arr[i];
		ptbucket->count++;
	}
	
	// 对每个桶中元素进行排序
	for (int i = 0; i < BUCKET_COUNT; i++)
	{
		Bucket *ptbucket = &adbuckets[i];
		int bucketSize = ptbucket->count;
		
		// 使用简单的插入排序对桶中的元素进行排序
		for(int j = 1; j < bucketSize; j++)
		{
			int key = ptbucket->padvalues[j];
			int k = j - 1;
			while (k >= 0 && ptbucket->padvalues[k] > key)
			{
				ptbucket->padvalues[k+1] = ptbucket->padvalues[k];
				k--;
			}
			ptbucket->padvalues[k+1] = key;
		}
		
	}
	
	// 合并桶中的元素到原始数组
	int index = 0;
	for(int i = 0; i < BUCKET_COUNT; i++)
	{
		Bucket *ptbucket = &adbuckets[i];
		int bucketSize = ptbucket->count;
		for(int j = 0; j < bucketSize; j++)
		{
			arr[index] = ptbucket->padvalues[j];
			index++;
		}
		free(ptbucket->padvalues);
	}
}
	
int main()
{
   /*  Write C code in this online editor and run it. */
    int arr[8] = {8,7,6,5,4,3,2,1};
	int n = sizeof(arr)/sizeof(arr[0]);
	
	printf("原始数组：\n");
	for(int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	
	bucketSort(arr, n);
	
	printf("排序后的数组：\n");
	for(int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");	

    return 0;
}